package problem;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * <p>
 *  给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
 *  解法1：Set集合三倍和原数组差值/2
 *  解法2：HashMap
 *  解法3：位运算
 * </p>
 *
 * @author fangXK
 * @since 2020-08-04
 */
public class S_137 {
    public int singleNumber(int[] nums) {
        Set<Long> set = new HashSet<>();
        long sumSet = 0, sumArray = 0;
        for(int n : nums) {
            sumArray += n;
            set.add((long)n);
        }
        for(Long s : set) sumSet += s;
        return (int)((3 * sumSet - sumArray) / 2);
    }

    public int singleNumber1(int[] nums){
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for (int num : nums)
            hashmap.put(num, hashmap.getOrDefault(num, 0) + 1);

        for (int k : hashmap.keySet())
            if (hashmap.get(k) == 1) return k;
        return -1;
    }

    public int singleNumber2(int[] nums) {
        int ones = 0, twos = 0;
        for (int x: nums) {
            // 之前出现过两次的，这次再出现就是出现了三次
            int threes = twos & x;

            // 之前出现过两次，这次没出现，是出现了两次。
            // 之前出现过一次的，这次再出现，也是出现了两次。
            twos = (twos & ~x) | (ones & x);

            // 统计记录出现了奇数次的，并从其中清除出现三次的。
            // 这样ones里面始终只会记录出现了一次的。
            ones = ones ^ x;
            ones &= ~threes;
        }
        return ones;
    }
}
